import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class IntCmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
public class TopKProblem {
    public static int[] smallestK(int[] array,int k) {
        //判断array是否为空，
        if(array == null || array.length == 0) {
            return null;
        }

        //判断K的值是否合法
        if(k <= 0 || k > array.length) {
            return null;
        }


        //定义一个大根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>(new IntCmp());

        //将前k个元素加入大根堆
        for (int i = 0; i < k; i++) {
            pq.offer(array[i]);
        }

        for (int i = k; i < array.length; i++) {
            if(array[i] < pq.peek()) {
                pq.poll();
                pq.offer(array[i]);
            }
        }

        //代码走到这里，大根堆中存储的是数组中前K小的元素


        //转化为int类型的数组
        int[] result = new int[k];

        int j = 0;
        for (Integer i : pq) {
            result[j] = i.intValue();
            j++;
        }

        Arrays.sort(result);
        return result;
    }

    public static void main(String[] args) {
        int[] array = new int[]{1,3,5,7,2,4,6,8};
        int k = 4;

        //预期输出1,2,3,4
        System.out.println(Arrays.toString(smallestK(array,k)));
    }
}
